#!/usr/bin/python3
# _*_ coding:utf-8 _*_

import random
from caltime import runtime


def insert_gap(ls, gap):
    for i in range(gap, len(ls)):
        tmp = ls[i]
        j = i - gap
        while j >= 0 and ls[j] > tmp:
            ls[j + gap] = ls[j]
            j -= gap
        ls[j + gap] = tmp


@runtime
def shell_sort(ls):
    d = len(ls) // 2
    while d >= 1:
        insert_gap(ls, d)
        d //= 2


lst = [random.randint(-1000, 1000) for _ in range(100)]
# print('原列表>>>', lst)
shell_sort(lst)
# print('排序后的列表>>>', lst)

